Shareware Universe - The Gold Collection

home *** CD-ROM | disk | FTP | other *** search

/ Shareware Universe - The Gold Collection / Shareware Universe The Gold Collection.iso / ray / rayce / rayce.doc < prev next >

Wrap

Text File | 1996-04-19 | 89KB | 2,731 lines

This file documents the Rayce 2.8 raytracer Copyright 1993,1994 Han-Wen Nienhuys This document describes version 2.8 of the Rayce raytracer. It was made from an info file. Copying ******** SEE THE FILE "COPYING" WHICH IS INCLUDED IN THIS PACKAGE. RAYCE IS DISTRIBUTED UNDER THE TERMS OF THE GNU GENERAL PUBLIC LICENSE Introduction ************* Rayce is a raytracer I've written to find out how raytracing works. It's written for purely educational purposes. If you want to make neat pictures, use PoV or Vivid instead. Oh, by the way, "educational" means "for my education", but you could use it in a C.G. class too. It wouldn't make a very good example, though, I am afraid. Most of the design and implementation is my own, our university library's copy of "An intro to Ray Tracing" hasn't been available for some time, so I was on my own, while programming Rayce. Still, Rayce has been expanded very much, and I plan to incorporate a lot of weird and new stuff into it. What features does Rayce have? - Rayce supports these primives: sphere, quadric, plane, lightsource, box, torus, algebraic, superquadric, polygon, triangle, disc - It has these non-primitives: composite, translational extrusion, CSG - Rayce has distribution raytracing for rendering penumbra, motion blur, gloss and translucency. - Rayce has multiple efficiency schemes (well :-): manual bounding hierarchies or recursive bintree traversal. - The sources are GPL-ed, and they're portably written ANSI C. - Debugging facilities - A POV like input language - Imagemaps What important features are still missing? - Solid texturing - Bumpmaps - Serious anti aliasing. - Support for these primitives * Heightfield * Bezierpatches * Cones * Blob Credits ******** Among others, these people have (knowingly or unknowingly) contributed to Rayce: George Kyriazis <kyriazis@turing.cs.rpi.edu> Rayce is based on a very small raytracer by George Kyriazis. You can still download this raytracer on wuarchive.wustl.edu, in the directory `/pub/graphics/graphics/ray/gk/' as `ray2*.shar.z'. This raytracer was called Ray, I've changed the name to avoid confusion. Besides, "ray" isn't a very original name for a raytracer, is it? (and "Raycer" was too obvious :-). Shawn McHorse <zaphod@fcircus.sat.tx.us> I would like to especially thank Shawn McHorse for valuable comments, bugfixes, the Rayce output in the SPD, the DJGCC compile and the new shading code. The POV-team In developing, I have used Persistence Of Vision, a great raytracer usually dubbed POV, as a shining example. That's why it looks internally so much like POV. The formulas from the `surfs.inc' were taken partly from a POV 2.0. include file. Mark Vandewettering <markv@cs.uoregon.edu> The color include, and the concave polygon code were taken from for Mark Vandewettering's MTV tracer. B.T.W. the colors look an awful lot like the X11 color database. Ben Trumbore <???> Most of the auto bounding for primitives is from: Graphics Gems III, Section VI.5, "rectangular bounding volumes for popular primitives," by Ben Trumbore, `bounding_volumes.c' David G. Hook, Bernie Kirby and ??? <echidna@munnari.oz.au> The Sturm sequence code in `solve.c' was taken from the raytracer Art, part of the Vort package (it is almost identical to the code in Graphics Gems I), by David G. Hook, Bernie Kirby and Peter McAree. The random numbers are also from Vort. Jochen Schwarze <schwarze@isa.de> The cubic and quartic solver was by Jochen Schwarze, and was taken from Graphics Gems I. Harm Hanemaayer <hhanemaa@cs.ruu.nl> The GIF reader was based on code from a GIF viewer by Harm Hanemaayer, and it was based on posting in rec.games.programmer in spring of 1993. Roy Hall <roy@wisdom.graphics.cornell.edu> The "angle" code in `shade.c' is based on parts of `D.c' from Roy Halls book on shading. Keith Bostic <harvard!seismo!keith> Keith wrote the public domain `getopt(3)', which is distributed for use on non-unix systems ??? Sung <???> He wrote the file `bsp.c' in GGems III: VI.1, Sung, "Ray Tracing with the BSP Tree", on which Rayce's bsp is based Invoking Rayce *************** The syntax of Rayce is simple: rayce [options] If you don't give options, it will print a small usage screen. You can use the following command line options: `-o OUTFILE' Specifies the output file, default: `output.tga'. The output format is 24 bit type 2 uncompressed Targa. `-i INFILE' Specifies the input file, default: `input.r'. `-l LIBPATH' Add LIBPATH to the list of library paths. These paths are searched for opening input files. Use multiple `-l' arguments for multiple paths. `-I #' Specifies the number of samples per pixel to use (default: use the number In the `options{}' block which is 1 by default). It's best to use a square, eg. 4, 16, 25, etc, as other numbers often cause. aliasing effects (try `lamp.r' with 5 samples per pixel). `-c' Continue a previously aborted trace; default: don't continue. `-x' Disable abort via keypress (default: allow abort). If you have compiled Rayce for a different computer than IBM PC running MS DOS, the `check_abort()' in your system sourcefile determines the abort condition. E.g. for Linux, this flag has nog effect. Interrupting should be done by sending a SIGINT (pressing Ctrl-C, killing Rayce, rebooting, etc.) `-h #' Specify image height in pixels, default: 50. `-w #' Specify image width in pixels, default: 50. `-d #' Turn on debugging. The number given is the sum of the debug flags you want to use: `1' switch on debugging for tokenizer. `2' switch on debugging for parser (`yydebug = 1') `4' switch on runtime debugging messages `8' print the interior (the scene, grids, optimisation data, etc.) after parsing `16' print the declarations (declarations, the scene, etc.) after parsing This only works if rayce was compiled with `-DDEBUG'. Default: no debugging info. `-t' Test flag, sets `test_flag' to `TRUE'. After a line has been finished, some statistics are printed, and after Rayce has finished tracing, more elaborate statistics are printed. Input Language *************** The input is based on POV 1.0 and 2.0 format. This chapter is an overview of the language. If you want the details, check out the sources, specifically `rayparse.y', the Yacc/Bison file which implements the parser. Okay, fasten your seatbelts: Basics ======= Comments are between `/*' and `*/'. Line comments are after a `//'. It is legal to nest the `/* */'. A float is what you would expect it to be: 1.2 12e-1 .12e1 all specify the same number. Additionally, you can use expressions for floats, these are the allowed operators in order of precedence from low to high: `+, -, /, *, ^'. An assignment to a variable is also an expression. Example: 12/10 0.12*10 1.0 + 0.2 1.2^2 - 0.14 #define a = - (- 1.2) #define b = ((a = 2) - .8) These expressions are all valid, and all specify 1.2. You can make a vector out of three floats: <FEXP1, FEXP2, FEXP3> FEXP1, FEXP2 and FEXP3 are floating point expressions. You can use expressions on vectors in the same manner as you can with floats: These are the allowed vector operations: `+,-' do addition and substraction. Use `*, /' for scalar multiplies and divisions, `^' for a vector cross product. From now on, I will use <VECTOR> to denote a vector. Use (<VEXP1>, <VEXP2>) |<VEXP3>| for the improduct and the length of a vector respectively; these are float expressions. The coordinate vectors are `x', `y' and `z'. Example: <1, 2/3, 4 * (x, <2, 0, 0>) > should give `<1, 0.6666, 8>'. Here is one other feature: <0.5> this will produce the vector <0.5, 0.5, 0.5>. Although this is not a customary notation in mathematics, it is very easy for specifying all kinds of shapes, eg. boxes, scaling factors, etc. Please note that everywhere two adjacent floats or vectors should be separated by a comma. Keywords should be in lowercase. Everything is case sensitive. Angles in your input file should be in degrees. Colors work the POV-way. For reasons of POV-compatibility, a `filter' part is allowed, but it will be ignored. The components can have any value, eg. negative values give "dark" colors. An extra feature is to convert colors from and to vectors. This makes adding and substracting colors easier. Example: These all give the same color. color red 0.5 green 0.1 color red 0.5 green 0.1 filter 0.5 color rgb <0.5, 0.1, 0> #define testcol = color red 1.0 green 0.2 color rgb 0.5 * <color testcol> Camera ======= Rayce has a simple pinhole camera, and it is lefthanded, similar to POV's camera. This camera can't be distorted, though. The viewpoint is specified by camera { CAMERA_DIRECTIVES } These can be a CAMERA_DIRECTIVE: `location <EYE>' EYE is the eye location. `sky <SKYVECTOR>' <SKYVECTOR> is the analogon of the POV sky vector. Your pictures will have their the top of your screen aligned to <SKYVECTOR> `direction <EYEDIR>' <EYEDIR> is the viewing direction. This is not used very often, since `look_at' is so much easier. `fov FOV' FOV specifies the vertical field of view angle in degrees. `aspect ASPRATIO' ASPRATIO is the aspect ratio of your picture (normal computer screens have aspect 4/3 = 1.333) `look_at <POINT>' `look_at' points the camera to towards <POINT>, while preserving the direction vector length (so the field is also preserved) Hope you understand this... A camera can be scaled, rotated and translated. Options ======== General options can be set from the opions block: options { OPTION_DIRECTIVES } These can be used as OPTION_DIRECTIVE: `time START, STOP' START and STOP specify the time interval in which the scene takes place: this is used with the `speed' vector from the object declaration. Default: START,STOP = 0,0. `background [<GRADIENT>] color BACKGROUNDCOLOR' <GRADIENT> specifies in which direction the gradient of the background color should be, and BACKGROUNDCOLOR is the color to use. If you don't want the gradient coloring, then use background color BACKGROUNDCOLOR. `depth DEPTH' DEPTH is the maximum recursion depth. Larger values will result in lengthier computations and more accurate results. Default: 3 `iterations NUMBEROFFRAMES' NUMBEROFFRAMES is the number of eyerays per pixel. If you want to use antialiasing, set iterations to a value greater than 1. This should also be done if you want to use distribution raytracing (If you are not familiar with this technique *note Distribution Raytracing::.). This value can be overridden by the `-I' command line option. Default: 1 `tolerance SHADOW_TOLERANCE' SHADOW_TOLERANCE is the minimum intersection distance: any intersection that is closer than SHADOW_TOLERANCE to the ray origin is ignored. By default it is 1e-3, and with simple shapes, you could make it as small as 1e-10. With certain shapes (notably high order surfaces, such as toruses), this needs to be bigger, otherwise numerical inaccuracies will find the intersection at x = t*dir + pos with t smaller than TOL. These are the intersections that should have t = 0. These intersections cause "phantom" shadows and digital zits. Default: 0.001. Larger values reduce fantom shapes, but they can eliminate correct shadows. The tolerance should be less the 1.0 (eg. 0.1) `antialias FILTERTYPE' Contributions of sampled rays are modulated with a FILTERTYPE. filter. `0' uniform filter `1' Gaussian filter `cutoff TRESHOLD' Adaptive depth control is done by specifying a cutoff THRESHOLD. If a ray would contribute less than a TRESHOLD fraction of the color written to the output, then the ray is not traced. This is called adaptive depth cutoff or adaptive depth control. Default: 0.0. Larger values will speed up rendering of scenes with a lot of refraction and reflection. `bunching BUNCHFACTOR' BUNCHFACTOR is the maximum number of objects that Rayce tries to stuff in a voxel or bounding volume if automatic efficiency is enabled. Default: 10 `optimisation OPTITYPE' Optimisation type Default: BSP: `1' manual optimisation `2' BSP Atmosphere ---------- atmosphere { ATMDIRECTIVES } Here, ATMDIRECTIVES is one of the following: `ior IOR' Index of refraction of the atmosphere. Default: 1.0 `ambient GLOBALAMBCOLOR' Global ambient color. Turn this up to make the whole scene brighter. Default: white Primitive Shapes ================= A primitive is a shape that is built into Rayce by the programmer. At the moment, Rayce supports the following primitives: Sphere ------ A sphere specified this way: sphere { <CENTER>, RADIUS } Here, CENTER is a vector, and RADIUS a float. The sphere is a special kind of quadric, and it is somewhat faster than a normal quadric, see `speedtst.r' for some info. You might expect a better performance of the sphere in comparison to the quadric. I guess, that's because I didn't use vector operations in `quadric.c'; instead I directly calculated the quadratic equation in t. See `quadric.c' if you don't understand what I just typed. (or you might just as well forget it :-) A sphere can be used in CSG; the inside of a sphere consists of the points X with: distance(X, CENTER) < RADIUS Polygon ------- You can make polygons in this way: polygon { <P1>, <P2>, ... } <P1>, <P2>, ... are the vertices of the polygon. Convex polygons will render a lot faster. Polygons do not have an inside or outside, and they're not closed, therefore a polygon cannot be used in CSG. The points should be in a plane. Cylinder -------- You can make a cylinder between <P1> and <P2> having radius R by inserting cylinder { <P1>, <P2>, R } This isn't really a primitive. If Rayce encounters a cylinder definition in its input, then it is converted to an extrusion of a circle with radius R. A cylinder can be used in CSG. Quadric ------- A quadric shape is a surface, which is described in this way: it is a set Q, with: Q = { (x, y, z) in R^3 | Phi(x, y, z) = 0 } In which Phi is Phi(x, y, z) = ax^2 + by^2 + cz^2 + dxy + eyz + fzx + gx + hy + iz + j = 0 or, more casually said: a quadric consists of points x, y, z for which ax^2 + by^2 + cz^2 + dxy + eyz + fzx + gx + hy + iz + j = 0 Therefore a quadric is a special kind of algebraic surface. If you'd take a = b = c =1, j = -1, and d, e, f, ... = 0, Q forms a sphere, with its center in (0, 0, 0), and radius 1.0. In general, the quadric is specified in same fashion as in POV: quadric { <COEFF1>, <COEFF2>, <COEFF>, CONST } The coefficients (a, b, c) form <COEFF1>, (c, d, e) <COEFF2>, (f, g, h) <COEFF3>, all of which are vectors. The constant j is `const'. You could also use an `algebraic' for specifying a quadric, but this is faster. Quadrics can be used as CSG element. For a quadric, the inside are points (x, y, z) with Phi(x, y, z) < 0. Plane ----- The plane is a shape mathematically defined by P = { X in R^3 | (X,n) = a } Here, (X,n) denotes the dot vector product of the normal n, and a point X on the plane. In Rayce and POV it is usually defined by plane { <NORMAL>, A } NORMAL is the normalvector to the plane, and A the distance in which it is moved along the normalvector. Note that the normal isn't normalised (which sounds quite funny if you read it aloud :-) The reason for this is that it isn't normalised in POV either. For the best results, always use a vector with length 1. A plane can be used in CSG. A plane is a closed, infinite shape. It has an outside and an inside. The outside of a plane is the part which is on the "side of the normal". symbolically: X is inside the plane if (X,<NORMAL>) < A This means, that both the inside and the outside are infinite. Box --- A box is CSG intersection of six planes. You should specify it using box { <POINT>, <OPPOSITE_POINT> } both POINT and OPPOSITE_POINT are vectors which correspond to two opposite corners of the box you want Rayce to produce. The box has its planes along the X, Y and Z axes. The order of the coordinates doesn't matter, so box { <1, 2, 3 >, <4, 5, 6> } and box { <1, 5, 3>, <4, 2, 6> } should look the same. A box can be transformed in the usual ways. Rotating it will slow down tracing a bit, though. A box can be used in CSG. A box has a proper inside and outside. Its inside is collection of points (x, y, z) which satisfy Min.X < x < Max.X Min.Y < y < Max.Y Min.Z < z < Max.Z Light source ------------ Light sources are the objects that cause diffuse and specular illumination, the things that make those nice shadows and highlights. Use them in this way: light_source { <ORIGIN> [LIGHT_MODIFIERS] } This is a point lightsource. The ORIGIN is the mandatory part: it tells Rayce the point from which lightrays emanate (actually, shadow rays are directed to the light source, but you knew that, right?). Light sources in Rayce cannot be seen. If you want to visualize them, enclose them with a shape which has the `no_shadow' flag. light_source { direction <DIR> [LIGHT_MODIFIERS] } This is a lightsource which casts light in one direction, <DIR>, and which is "infinitely far away". It doesn't cast any shadows. These are the allowed `light_modifiers': `color LIGHTCOLOR' This tells Rayce to give the light source the color LIGHTCOLOR. Default: white `fogsource' One can produce fog emanating from one point with `fogsource'. The effect looks like a lightbulb in the fog. Default: not a fogsource `direction <DIR>' Sets the direction of a lightsource to <DIR>. `point_at <TARGET>' This will point lightsources to <TARGET>. ie. direction DIR is adjusted to point from <ORIGIN> to <TARGET>. `tightness TIGHT' Controls the tightness of fogsources and spotlights. (default: 0, no directional effects) `no_shadow' The lightsource doesn't cast shadows, but the highlights and diffuse illumination remain visible. `attenuation FALLOFFEXPONENT' FALLOFFEXPONENT is the exponent to use for fading light: in real life, the intensity of light diminishes with the distance; the intensity is proportional to 1/r^2, so in real life the FALLOFFEXPONENT is 2. Light in Rayce will diminsh with 1/r^FALLOFFEXPONENT. By default it is 0, i.e. the intensity does not depend on the distance from the light source. `radius RADIUS' Rayce can do penumbra (soft shadows) as well. Use radius RADIUS to specify the radius of a discshaped lightsource. (default: radius is 0, no penumbra). Don't forget to turn up the number of rays per pixel. If you're interested: the intensity at an intersection point is calculated with (lightdir, DIR)^TIGHT * (1/r)^FALLOFFEXPONENT Here r denotes the distance to the light source, (,) is the dot product. Lightdir is the vector from the intersection point to the lightsource. Lightsources cannot be used as part of a CSG. For POV compatibility `spotlight' is also allowed, but it doesn't have any effect. Triangle -------- A triangle is specified this way: triangle { <P1>, <P2>, <P3> } P1, P2 and P3 are the vertices of the triangle, and the order in which the points are specified does not matter. No backface culling is done, and these are ordinary triangles, i.e. normals aren't interpolated, if you want that, use smooth triangles. A triangle cannot be used in CSG. Smooth triangle. ---------------- A smooth triangle (a.k.a. triangular patch) with interpolated normal vectors is represented in this way: smooth_triangle { <P1>, <N1>, <P2>, <N2>, <P3>, <N3> } <P_I> denote the vertices, and <N_I> denote the normals at these vertices. A smooth triangle cannot be used in CSG. Torus ----- A torus is a shape that looks like a donut. A torus is specified like this: torus { MAJOR, MINOR } MAJOR is the major radius, and MINOR is the minor radius. The torus produced lies in the XZ plane, so you have to rotate it if you want another direction. Technically speaking, a torus is a circle in the XZ plane with radius MINOR and center <MAJOR, 0, 0>, swept around the Y axis. Don't try to use `bounded_by' on toruses. The torus is already enclosed in an intersection of a minimal bounding sphere and two planes. A torus is a quartic surface. Among others, this means that a torus can at most have 4 intersections with a ray. For calculating these intersections, by default, a technique known as Ferrari's method is used. Although this technique is relatively fast, it can give surface acne because of numerical inaccuracies. The acne is sometimes called "digital zits", black dots -- try a zoomed in version of the `papercl.r' with `tolerance 1e-5', and no `sturm' keywords. If this happens to you, then try adding the keyword `sturm' after the definition. A different method --Sturm sequences-- for calculating intersections will be used, which is slower, but more accurate. Alternatively you can set SHADOW_TOLERANCE *Note Options:: higher, eg 0.05. This won't make the calculations more exact, but it will take away most of the phantom shadows. Don't make tolerance too big. It should be smaller than one. A torus can be used in CSG. The inside of a torus (donut) is the part where the jelly and dough usually resides. If MINOR > MAJOR, then weird things will happen. Check out the source. High order surfaces. -------------------- You can model arbitrary algebraic (polynomial) surfaces using Rayce. Anything is allowed, as long as the order is less than 12 (if you'd like more, then you'll have to recompile; change `MAX_ORDER' in `ray.h' to suit your needs). It is specified with algebraic { $ PHI $ [ALG_MODIFIERS] } The algebraic surface S is determined by a polynomial Phi. The surface is the set S for which S = { (x, y, z) | Phi(x, y, z) = 0 } In Rayce you get such a surface by defining Phi(x, y, z) by PHI, or specifying algebraic { $ PSI(X, Y, Z) = CHI(X, Y, Z) $ } Which means that Phi := Psi - Chi. so Phi is a polynomial in x, y and z. A point is inside the algebraic if Phi(x, y, z) < 0. You can perform the following operations on x, y and z to form new polynomials: addition, eg. x + y + 83 substraction, eg. x - z - 83 exponentation, eg. y ^ 4 multiplication, eg. 5 * x * y grouping, eg. (x+y)^2 Notice that only floating point numbers are allowed, and no expressions. Example: $ 1 + 2 $ // ok, we're adding the polynomials 1 and 2 $ (x, y) $ // WRONG, (x, y) is a float-expression not a // float $ 1*x $ // ok $ 1/2 $ // WRONG, you can't divide polynomials (not // even 1 and 2 These are the allowed ALG_MODIFIERS: `closed' This keyword is for speeding up inside/outside calculations. Use it on closed and finite surfaces. Default: not finite and closed `sturm' Use the accurate yet slow sturm sequence solver. (default: rootfinder is the ordinary Ferrari rootfinder) If you insist on using expressions, then use defined floating point constants. Example: #define R = 1.0 #define r = R/2 #define mytorus = algebraic { $ (x^2 + y^2 + z^2 + R^2 - r^2)^2 = 4*R*(x^2+y^2) $ closed } In the above, mytorus is defined as a torus with minor radius 0.5, and major radius 1.0. Example: algebraic { $ x^4 + y^4 + z^4 -1 $ closed sturm } This should specify a closed and finite surface (in this case a superquadric; a cube with rounded corners), and it is to be calculated using Sturm sequences. Since an algebraic is stored in terms of operations, algebraic { $ (x-1)^2 + y^2 - 1 $ } is calculated differently from algebraic { $ (x^2 -2*x + 1) + y^2 - 1.5 + 0.5 $ } The latter requires more operations, and thus it is more expensive. Try to make your formula as compact and efficient as possible. An algebraic can be used as a CSG part. The inside is defined by (x,y,z) for which Phi(x,y,z) < 0 Superquadric ------------ A superquadric is a generalized sphere. For more information, consult `superq.tex'. It looks like |x|^P + |y|^P + |z|^P = 1 if p is large, then this forms a cube, with faces parallel to the axes and rounded corners. if p = 1, it's a cube with corners in <0,0,1>, <1,0,0>, <-1,0,0>, etc. if p = 2, it's a sphere. This is how you coerce Rayce in rendering one: superq { <P> } NB. If P < 1, then you still get a shape, but since the shape then is not convex anymore, and the intersection algorithm used won't work reliably; You probably won't get a good render, if you try: superq { <0.5> } In Rayce the above is generalized. The algorithm for computing intersections with superquadrics works for arbitrary shapes C1(x) + C2(y) + C3(z) = 1 If C1, C2 and C3 are convex functions. So in Rayce, you can also render elements from this class of shapes: |x|^P1 + |y|^P2 + |z|^P3 = 1 where P1, P2 and P3 are all greater than 1. This is how you specify it. superq { <P1, P2, P3> } A superq can be used in CSG. Discs ----- Discs are round shaped pieces of a flat planes, they could be simulated with a plane `clipped_by' a sphere, but they have been put in on special request from Shawn McHorse. Syntax: disc { <CENTER>, <NORMAL>, RAD } The above is a simple disc disc { <CENTER>, <NORMAL>, MAJRAD, MINRAD } This is a disc with a hole in the center. A disc cannot be used in CSG. Transformations --------------- * All primitives may transformed using `scale', `rotate' and `translate'. Example: sphere { <0>, 1 // now it's a sphere scale <1,2,1> // now it's an ellipsoid translate x rotate 90*x } * Every shape can have its own private texture. * Every shape which has a proper inside and outside defined, can be inverted using `inverse'. Non-Primitive Shapes ===================== Non-Primitive shapes are shapes, that can be used to form new shapes from existing shapes. Currently these are supported: CSG --- CSG is a term coined for a very useful modelling tool. CSG --Constructive Solid Geometry-- enables you to add and subtract objects, thus forming new objects. These are the shapes that can be used as a CSG part: sphere box torus extrusion (make sure it's closed! ) cylinder (idem ditto) conic (idem ditto) superquadric The above shapes all have finite (bounded) insides. In jargon, you'd say that they are manifolds. Although the following aren't necessarily finite, you can still use them in CSG as they are closed. quadric plane intersection union algebraic Generally: any closed shape can be used as a csg element. You'll be warned if you try to use a non-closed shape. The above mentioned surfaces (sphere, quadric etc.) have the following two properties Firstly, they divide the whole of 3D space into two distinct pieces (sets): an "inside" and an "outside". Every point lies either inside or outside the shape. Theoretically, a point could be on the frontier of the inside and outside, i.e. on the surface itself. Due to numerical inaccuracies and implementation, this rarely happens. Of every ray tested agains a CSG, only origin + 2*tolerance * direction is tested for inside/outside. So if you want to create quirky images, make sure you have intersections with CSG parts at distances d with tolerance < d < 2*tolerance. (So be warned! :-) Some special primitives, like the torus or the sphere, don't need this testing: if a ray intersects the shape an even number of times, then the rays origin lies outside the shape, if the ray has an odd number of intersections, then its origin is inside. Secondly, one would walk along a ray, a change inside/outside of a shape happens if and only if the ray hits the surface. The surface is "closed". Other CSG algorithms can also use triangles and discs for CSG, but this one cannot, because a triangle fails the second property. WARNING: try to avoid CSG wherever possible. Usually,a composite instead of a union will also do. In that case use the composite, not the union, a composite is really faster, and it is optimised in automatic efficiency. CSG Union --------- Union is a CSG operation, it merges two shapes into one. A point is contained in the inside of a CSG union of S1, S2, ... if and only if the point is inside at least one of S1, S2, ... Syntax: union { CSG_ITEMS } Note that Rayce has a real union. That is, if you do union { sphere { <0, 0, 0>, 1 } sphere { <0, 0, 1>, 1 } } the interior walls are removed: if you are standing in the the first sphere, facing the second sphere, you can actually look inside the second sphere. CSG Intersection ---------------- Intersection is another CSG operation. If you do an intersection of N shapes, then only points that are contained in all N shapes simultaneously, are part of the intersection. So a point is inside a CSG intersection of shapes S1, S2, ... if and only if the point is inside S1, and S2, and S3 and .... Actually, you can only see the boundary of this intersection. An intersection looks like this: intersection { CSG_ITEMS } CSG_ITEMS is one of `shape' One of the allowed CSG shapes. `inverse' This flips a shape inside out. Check out the mathematics section for details. The `inverse' keyword flips a shape: the inside of #define B = shape { A inverse } has all points which are outside of A, and the inside of B has all points which are outside of A. Mathematically speaking, taking the inverse of a shape, is equivalent to taking the complement of the set, formed by a shape. `transformation' It is legal to transform CSGs with `rotate', `scale' and `translate'. In effect, you are then transforming all components of the CSG, as far as they have been specified. `texture block' Adding CSG a texture means the children of the CSG inherit this texture if they don't already have one. Extrusion --------- You can extrude 2d curves with Rayce: Say, you'd want to make a column for use in a roman temple. One option is to use a cylinder like this: define column = object { Disk_Z scale <1, 1, 20> } // now using CSG But you could also regard a cylinder as a circle in the XY plane that is that is "thickened" along the Z axis. A circle in the XY plane is the intersection curve of a sphere and the XY plane. So you could also use: define column = extrusion { 20, sphere { <0>, 1 } } In general, the syntax of an extrusion is: extrusion { HEIGHT shape { ... } } This takes a shape, and extends the intersection of the shape with the XY plane to the Z-direction. Your extrusion will have height HEIGHT. HEIGHT should be bigger than 0. For instance, if you have defined the projection of a cogwheel on the XY plane, then you could make a 3d object out of it by specifying extrusion { 1 intersection { cogwheel } } NB. This is not exactly the same as Polyray's sweep. Polyray extrudes polygonal curves or spline curves, and you can vary the direction of the extrusion in Polyray. Conic extrusion --------------- conic { <APEX>, HEIGHT SHAPE { } } Conic extrusion of SHAPE, with apex in <APEX>, height HEIGHT, clipping planes parallel to XY plane. BETA! DOES NOT WORK! Transformations --------------- * You can transform a nonprimitive shape using `translate', `rotate', and `scale': the composite is transformed. This means that its bounding shape is transformed, and its objects and composites are transformed. * Translation, rotation and scaling will only affect a CSG as far as it has been specified. For more information, look at the definition of hexagon in `shapes.inc'. * All nonprimitive shapes (composites, CSG) can have their own texture. Textures ========= Rayce's textures have more freedom than POV's: every surface characteristic can have its own color. Although this isn't realistic, it can give nice effects. I haven't implemented procedural textures yet, so checker- or marbletextures are not possible. For now, use an imagemap. Textures have the following syntax: texture { [texture_modifiers] } A `texture_modifier' is one of the following: `ambient AMBCOLOR' AMBCOLOR will be the ambient color. Default: black. `diffuse DIFFCOLOR' The diffuse color is set to DIFFCOLOR. Default: black. `specular SPECCOLOR' The color of a shiny highlight is set to SPECCOLOR. In POV this is always white. Default: black. `microfacet DISTRIBUTION' Rayce has different microfacet distributions built in. At the moment the following are supported. The syntax has been copied of Polyray, but the keywords have been defined in `standard.inc'. `Phong' Phong is the default distribution. Although it is said to not realistic, it a fairly common distribution. It usually gives a platic like appearance. `Blinn' POV's roughness, a distribution function similar to Phong's `Cook' (a.k.a. Beckmann) `Reitz' (Trowbridge) `Gaussian' The normal (from statistics known) distribution The tightness of the highlight is derived from the roughness of the surface. It can be set `roughness'. `roughness ROUGHNESS' It defaults to 0.0. (very small highlight, can't be seen) You can adjust this manually, or you can use `angle'. The rougher a surface, the bigger the "hot spot". `angle ANGLE' `roughness' will be set, to produce a highligh that has 0.5 of its maximum intensity at an angle of ANGLE. Smaller values for ANGLE produce tighter highlights. `reflection REFLCOLOR' makes the surface reflect an AMOUNT part of the light, and it uses a REFLCOLOR filter. default: no reflection, black `refraction REFRCOLOR' makes the surface refract a REFRCOLOR part of the light. Default: black, no reflection. `ior IOR' IOR is the material's index of refraction. Default: 1.0 `refract_angle ANGLE' ANGLE is the maximum deviation for refracted rays. This causes a blurred refraction, a.k.a. translucency. `reflect_angle ANGLE' ANGLE is the maximum deviation for reflected rays. This causes a blurred reflection. a.k.a. Gloss. `specular AMOUNT' `ambient AMOUNT' `diffuse AMOUNT' `reflection AMOUNT' `refraction AMOUNT' This scales the current specular, ambient, diffuse, reflection, refraction color by AMOUNT. For POV compatibility you can also specify `color COLOR' This sets all colors (refraction, reflection, diffuse, ambient, specular) to COLOR, and the intensities to the default values used by POV. (ambient 0.2, diffuse 0.6, etc.) From then on, these work POV compatible: You can also use `specular AMOUNT' This sets the specular color to AMOUNT. The same can be done for the other colors: specular AMOUNT ambient AMOUNT diffuse AMOUNT reflection AMOUNT refraction AMOUNT Here is an example: #declare New_Brass = texture { color red 0.70 green 0.56 blue 0.37 ambient 0.35 diffuse 1.00 brilliance 15 specular 0.41 roughness .2 } `imagemap { ... }' You can specify an imagemap. An imagemap wraps a bitmap picture onto a of the CSG, as far as they have been specifiedshape. This is the syntax: image_map { FILETYPE FILENAME IMAGE_MAP_MODIFIERS } This maps the file FILENAME onto the shape. FILETYPE is the type of the image which is in FILENAME. The following types for FILETYPE are supported: `tga' this specifies a targa 24 bit uncompressed type 2 (the same type Rayce outputs) `gif' This specifies that the image is a standard gif file. IMAGE_MAP_MODIFIER is one the following: `map_type TYPE' tells how the image should be wrapped around the object. TYPE is one the following. The keywords are defined in `standard.inc'. `Plane_Map, 0' maps the image onto the XY plane `Sphere_Map, 1' maps the image onto sphere centered in (0, 0, 0) `Cylinder_Map = 2' maps the image onto cylinder along the Z axis. `Torus_Map, 5' maps the image onto a torus lying in the XZ plane, radius 1.0 `uvswap' swaps the u and v parameters. This is identical to rotating the bitmap 90 degrees. `uvrange' UR, VR This scales the bitmap down by UR, VR, ie. image_map { "marijke.gif" map_type 3 uvrange 2 2 } will cause `marijke.gif' to be shrunk, until it fits 4 times on a torus (two times along the big equator, two times along the small one) `uvoffset UO, VO' This translates the image by UO, VO. `once' If `once' is set, then the image can be seen only once. `interpolate INTERPOLTYPE' If you specify `interpolate' then interpolation is turned on. For POV compatibility, the interpolations should be followed by a integer INTERPOLTYPE. This is 0 for no interpolation (default), anything else for interpolation. The interpolation is bilinear, anything else is not supported These values are defined in `standard.inc'. `usenormal' This tells Rayce to use the surface normal instead of the object coordinate as an indexing point. The color of an imagemap at (x, y, z) in R^3 is computed as follows: 1. First find u and v for the desired image. 2. Swap u and v if uvswap is set. 3. Scale: u = u*UR, v = v*VR 4. Translate: u = u + UO, v = v + VO 5. Determine color: 1. if (once) and not (0.0 <= u, v <= 1.0) then return black. 2. Get color at (u, v) in the image. If interpolation is turned on, then interpolate colors, else round the u, v coordinates and use that coordinate Textures can be scaled, rotated and translated. Texture Hierarchy ================= If an object doesn't have a texture, then Rayce gives it the texture of of the CSG, as far as they have been specifiedits father. Objects in Rayce have a hierarchy. #define C = union { A B } union { C } In this example, A and B are children of C, and C is a child of the whole scene. If Rayce registers a hit with primitive A, then it first looks at A's texture. If A doesn't have a texture, Rayce checks C for a texture. If C doesn't have a texture, then the Rayce checks C's daddy. C's daddy is the whole scene, and the whole scene always has a texture, the default texture. You can change the texture by putting this in your input file: default = texture { TEXT } This will make TEXT the default texture. Take a look at `hier.r' for an example of hierarchic textures. Objects ======== In Rayce, objects are specified in this manner: SHAPENAME { SHAPE_BODY } or object { SHAPENAME { SHAPE_BODY } } SHAPENAME is one of the allowed shapes or a composite, SHAPE_BODY the statements with info about the shape in it. The difference between these two ways of specifying is: you can use of the CSG, as far as they have been specified`speed' and bounding shapes with the latter. Composites ========== Rayce supports composites as well. A composite collects a bunch of shapes, and treats them as one. This makes transforming and handling a lot easier. A composite's syntax is the same as POV's: composite { [OBJECTs|COMPOSITEs] } Example: composite { box { <-1, 1, 1>, <2, 3, 4> } object { heike } composite { Dikkerd } } Object Modifiers ================ These transformations and on objects and composites are legal: `texture { ... }' An object can have a texture. Example: object { sphere { <0, 0, 0>, 1 } texture { ambient color red 1.0 } } This is equivalent to sphere { <0, 0, 0>, 1 texture { ambient color red 1.0 } } `scale' `rotate' `translate' Any object can be transformed with `scale', `rotate' and `translate'. Translation, rotation and scaling will only affect a CSG or composite as far as it has been specified. All other modifiers apply to all contents in a composite or CSG. For more information, look at the definition of hexagon in `shapes.inc' `inverse' Invert a shape. This is only useful with csg-able shapes. `no_shadow' The object (and its children) are invisible to shadowrays. This object does not block light `no_eye' The object (and its children) are invisible to eyerays. You can only see this object in reflections,refractions and shadows. `no_refract' The object (and its children) are invisible to refraction rays. You cannot see this object through refractions `no_reflect' The object (and its children) are invisible to reflection rays. You cannot see this object through reflections `speed <VELOCITY>' This says the composite will have a speed. This is implemented by adding VELOCITY to the speed of each object in the object and its children. This acts on the shape as far as it has been specified. Note that only the bounding shapes of the noncomposite objects ("the leafs in the tree") are moved along. So be careful about your bounding shapes with moving objects. This is why I sometimes find this motion blur a pain the reet, because it makes all kinds of stuff extra complicated. For a nice and smooth picture, don't forget to turn the number of frames from the `options {}' block up. Note: this motion blur is only linear. Implementing rotational blur is very expensive, so I haven't implemented it. Example: object { sphere { <0, 0, 0>, 1 } speed <0, 0, 1> } composite { composite { fubar } object { fubular } bounded_by { box { <-1, -1, -1>, <1, 1, 1> } } speed <0, 0, 1> } However, this is not allowed: sphere { <0, 0, 0>, 1 speed <0, 0, 1> // WRONG! syntax error } `bounded_by { ... }' Manual bounding shape bounded_by { BOUNDINGSHAPES } This means that the composite is bounded by BOUNDINGSHAPES. A lot of shapes, especially compound shapes, take up a lot of time. To speed this up, you can specify bounding shapes: simple shapes that encompass a much more complex shape. This bounding shape should be closed; my suggestion is to use a sphere or a box, if possible. If an object has bounding shapes, then all rays are first tested against these shapes, in the order which they have been specified. If this intersection test fails, or closer intersections have been found previously, then the object itself is not tested. If the optimisation automatic (eg. BSP), and the object is a normal element of the scene (not a part of CSG, extrusion, conic etc), then the bounding usually is ignored. It is used to determine the extent of a shape. If Rayce complains about an infinite shape that cannot be autobounded, then there are two options: 1. The shape is really infinite, then it is best to leave it that way. Example: if you replace an infinite groundplane, with a large disk, then the tracing will be slower. 2. The shape is finite, and not big compared to the rest of the scene. Then you should use `bounded_by'. Example: object { algebraic { $ x^4 + y^4 + z^4 - 1 $ } bounded_by { box { <-1>, <1> } } } composite { composite { fubar } object { fubular } bounded_by { box { <-1>, <1> } } } This is not allowed: algebraic { $ x^4 + y^4 + z^4 - 1 $ bounded_by { box { <-1>, <1> } } // WRONG! syntax error } `clipped_by { ... }' This clips the object with a shape. Syntax: clipped_by { CLIPPINGSHAPES } The object is clipped by CLIPPINGSHAPES. A clipping shape is the Procrustes in raytracing: Rayce cuts off all parts of an object that stick out of the CLIPPINGSHAPES. If you want to use a shape as bounding shape and clipping shape simultaneously, then you should use clipped_by { bounded_by } Example: #include "shapes.inc" object { object { Cylinder_X } // now it's infinite clipped_by { box <-1, -1, -1>, <1, 1, 1> sphere { <0, 0, 0>, 100 } } // now it's a tube, and you can look inside. } composite { composite { fubar } object { fubular } bounded_by { box { <-1, -1, -1>, <1, 1, 1> } } clipped_by { bounded_by } } Special Commands ================= If your scene file says: #include "foobar.inc" then the parser will act as if the contents of `foobar.inc' are inserted at this point. The `#' is optional: since the POV team hasn't made it mandatory, all `#'s in the input are treated is whitespace: they are ignored. If a file is opened, `[' is shown, and an "operator pacification indicator" (`.') is printed every 25 lines read, after a file has been read `]' is printed. If you use objects, cameras, etc. a lot, you should `#define' them, and put them in an include for the greater benefit of the human race: #define foo = sphere { <0, 0, 9>, 1 } means you can use object { foo } instead of object { sphere { <0, 0, 9>, 1 } These can be defined: any shape: #define foo = sphere { ... } camera: #define foo = camera { ... } color: #define foo = color ... texture: #define foobar = texture { ... } vector expressions: #define fub = <0, 1, 0>^<1, 0, 0> floating point expressions: #define blab = 1.34/2 image_maps: #define auk = image_map { ... } The following obfuscated construct should work correctly: #define foo = object { sphere { bla } texture { foo } } If you attempt to save memory, then don't use defines: they only cost more memory during the parsing stage. You can use the keyword `declare' instead of `define'. The effect on Rayce is the same. Rayce has no CPP preprocessor, so the `define' stuff doesn't have to be on one line. I think the latter is better. As a bonus, a `#define' at the start of a line is recognized by certain utilities for the C programming language (eg. [ce]tags) POV compatibility ****************** Rayce started out as an experiment, and the POV language seemed simple to implement. That's why the syntax looks like POV so much. When I designed it, POV 2 wasn't out yet, so it's not completely compatible. The format is loosely based on POV1. I call it semi-POV compatible. These are incompatibilities: [note. I don't use POV that often anymore, there are probably some things which aren't correct] What Rayce misses: * solid texturing * bumps * serious antialiasing. * `phong' syntax: use the `microfacet' directive * support for these primitives - Heightfield - Bezierpatch - Cone - Poly/Cubic/Quartic (the `algebraic {}' allows you to do the same, but with a better syntax) - Blob * difference (use an intersection and `inverse') * `filter' color components Caveats with porting scenes * don't use pigment/normal/finish blocks; use POV1 style texture blocks. * The color of a texture should be the first with POV style textures. * camera model is slightly different. Use `aspect' for aspect ratios * in POV2, `unions' are called `merges', and `composites' `unions'. So a POV2 merge corresponds with a Rayce union, and a POV2 union corresponds with a Rayce composite. What Rayce has (and POV doesn't) * more flexible texturing for even colors. * these primitives: - extrusions. - polygons. - superquadrics. * ability to manipulate imagemaps with uvswap, uvrange, etc. * motion blur. * gloss, translucency. * light that attenuates with the distance. * microfacet models * fog sources. Syntax incompatibilities Usually, Rayce's syntax is more relaxed. These are extras: * <a> as vector exp. * this is legal: composite { object { bla } rotate 30*y object { bla } rotate 30*y } Technical Stuff **************** This is supposed to be a more detailed doc file about the technicalities of Rayce. It is under construction (as is everything in Rayce :-) About The Sources ================== I've tried to continue the Ray-tradition: I've commented the sources to my best ability, and I hope I didn't obfuscate the sources too much. All sources have been formatted with GNU indent (see the file `cformat'). I have always use 132 x 43 screen resolution, so some of the source will not be very readable in 80x25.... Get yourself a serious VGA card :) Compiling ========== Remember these if you attempt at compiling Rayce: 1. Get a ANSI compliant compiler. I don't know wether it will compile on non ANSI compilers, but it will undoubtedly give problems. 2. I've tried to keep all device/compiler dependent stuff in a separate file. A generic version of this file is in `dvi.c'; it provides only the stubs for the functions. If you want to port Rayce, then make a new Makefile and a replacement for the systemfile. look at `ibmtcc.c' or `linux.c' to see which functions it should have, and what they should do. It would be nice if you sent me a copy of the source, and the makefile. If you are very lazy, you can use `dvi.c'. The `linux.c' file only uses ANSI standard routines, so you should be able to use `linux.c' for most OSes which have signals. These files are provided: `makefile.tcc, ibmtcc.c' for Turbo/Borland-C++ `Makefile, linux.c' for Linux `makefile.dj, djgcc.c' for DJGCC (the port was done by Shawn McHorse <Zaphod@fcircus.sat.tx.us>) 3. Although I tried to avoid system dependent code outside the systemfiles, there are some exceptions: * the naming of MSDOS is somewhat braindead, so in `token.c', there is a bit of conditional compilation for including `rayparse.h' instead of `rayparse.tab.h' under MSDOS. * in `rayparse.y' it says #ifdef __TURBOC__ #define alloca allocaa #endif 4. Make sure that Rayce has enough memory. In MSDOS this means: a reasonable stack size, and a large memory model. Turbo C's 4k stack is definitely too small, but 16k suffices. 5. Get some variant of Yacc. I use Bison, but any other Yacc will probably also work. If you use Bison, and your compiler has no `alloca()' function, you'd better define alloca to be allocaa in `rayparse.y'. Turbo C doesn't have `alloca()', so I made a fix: memory obtained `allocaa()' is freed after `yyparse()' has exited. 6. If you use Linux, it is very easy, just type make sRayce for a speedy version of Rayce. Source Description 1 ===================== `ray.h' typedefs and important `#defines' for Rayce. The most important ones: `object': This is the main structure. It holds shape data, textures, boundingshapes. It has a `next' field, so it can easily be linked into a linked list. `struct ray': this is (of course) the ray. It is a line, starting at ray.pos, headed for ray.dir. A few important notes: If you want to study the sources of Rayce, you'd better start reading here. A function or variabele that is local to a file is called `PRIVATE'. A function or variabele that can be accessed from the whole program is called `PUBLIC'. The vector as well as the color are structs, not arrays, so they must be passed by pointer, if function wants to change them. But the advantage is, they can be returned from a function. `object.h' a collection of `struct xxxx_data's; structures which hold info on shapes, textures, etc. eg. sphere_data contains a radius and a center. `proto.h' This file contains function prototypes, to avoid the compilers' weird ideas about default prototyping. Modifying its contents usually is harmless, so the makefile just ignores it. `extern.h' Global variables. Because this header is included more than once, all variables have been declared as `EXTERN', which is defined as extern. In `initialize.c', `EXTERN' is undef'ed, and included again. So storage for global variables is only allocated once. Important ones: commandline options, statistics. `parse.h' for communication between `rayparse.y' and `token.y' `rayparse.y' The Bison sources for the parser. `rayparse.c' `rayparse.tab.c' `rayparse*.h' Bison generates these files from `rayparse.y'. I don't distribute them, because you can generate them yourself in a few seconds. `vector.h' Vector macros. They usually have this form vectormacro(output, input1, input2). Take care: usually a construction like `vsub(a,a,b)' (equivalent with a:=a-b) works fine, but you can't do this with vcross. [Yes. I know, GCC allows inline functions, but I don't want to go through all the hassle and compiler dependent code.] `macro.h' Other useful macros. `ibuf.h' Macros for the intersection queues. `token.c' Tokenizer, handles includes and allocation of declares. The most important function is `yylex()'. The rest are little bits. If you add keywords to the syntax, then add it into the big table in this file. The keywords should in alphabetical order. `messages.c' Error messages, debugging logs and memory allocation routines: `errormsg()', `warning()', `dprintf()'. `rayparse.y' This is the Yacc/Bison source file. Run `bison -d rayparse.y' to get `rayparse_tab.c' and `rayparse.tab.h'. On MSDOS systems these names will be truncated to `rayparse.c' and `rayparse.h'. `raymath.c' Linear algebra and simple mathematics: vector math, matrix math, random generators. `ibmtcc.c' `linux.c' `djgcc.c' `dvi.c' Compiler/system specific parts: timing, handlers, abort checks. Although they are still pretty portable, you could substitute `dvi.c' for this one, if your compiler has complaints. If you would like to code display routines, this is where you should add them. I myself don't like device dependent stuff in a program which is supposed to be highly portable. `main.c' The file containing `main()' it scans the command line, prints notices, calls the parser and starts the tracing process. `trace.c' Sets up the tracer, walks all the pixels, and calls `trace()' for each pixel. Ray sampling is done here, and stat printing is done here too. `intersect.c' Small file with main intersection routine: it does the intersection with the whole scene, and then fills in the details such as intersection points, normals. The shadow test is a separate routine, because it has to deal with shadow caching, early exit for blocking objects, etc. `initialize.c' Initialization and stuff which I can't put somewhere else. Global storage allocation. `bg.c' Compute a background color, maybe too small to be a separate file, and too fancy. Who needs gradient background? Also adds fog influence to traced rays. `poly.c' Manipulations of polynomials in one variable: addition, multiplication, negation, power, etc. Used by `solve.c' and `algebraic.c'. NB. If you want to do q(x) := q(x) - t(x), then `poly_sub(q, q, t)' is OK. But `poly_multiply(q,q,t)' for q := q*t is not! `solve.c' Solve polynomial equations of arbitrary order. NB. It's main entry point is the function `solve_rt_poly()' which finds positive roots of a polynomial, and puts them sorted in an array. If possible, solve_rt_poly uses fast root finders for 2nd, 3rd and 4th order equations. If you want to have accurate results, use `sturm_solve_rt_poly().' The code was done by the collective Eric H. Echidna (who have written a nice raytracer called Art). I also added bits of myself and Graphics Gems. Ok. It's not my code, but I'll try explain what this is all about. This module solves polynomial equations, or equations that look like: a_n x^n + a_(n-1) x^(n-1) + ... + a_0 = 0 n is called the order of the equation, is denoted by `ord' in the code. Note that any solution p(s) = 0 to the equation also is a root of the polynomial: if p(s) = 0 is a solution, then the polynomial can be written as p(x) = q(x) (x-s), with degree(q) = degree(p) - 1. In this application we are only interested in so called "simple roots", i.e. if s is a root ( p(s) = 0 and p(x) = q(x) (x-s) ), then q(s) != 0. This has numerical reasons: take (for example) p(x) := (x-1)^2. p clearly has a double root: p(1) = 0. But if we would start calculating, intermediary results would look like it came from p(x) = (x-1)^2 + 1e-20, which has no solutions. So double roots can be hard to detect. If n <= 4, then an "exact" solution is possible: an out of the box solution is possible. However, it is numerically unstable. It has been proved that for n > 4, no general exact solution method exists. If n > 4, we have to resort to numerical techniques. The first attempt used was `equation_solver()', which has been `#undef''d ^H^H^Hdeleted, since it is 3x slower for quartics than sturm sequences. It worked like this: let us assume p(t) = 0 is the equation we want to solve. 1. if degree <= 3, then solve exactly 2. if degree > 3, then take derivative, (recursive) find it's roots with `equation_solver().' These roots of the derivative are the extrema of p(t). We then calculate these extrema. Additionally, p(0) and p(LARGE) are boundary extrema. Any zero of p would lie between two extrema with different sign, and (vice versa) Between two extrema with different signs there always is a zero. We can find such a zero with binary chop. The sturm sequence uses also this property: A sturm sequence can be used to detect sign changes of p(x) for x in the interval [a,b). A sturm sequence is a sequence of polynomials, p_0, p_1, ... p_m because it's a sturm sequence, these polynomials have special properties. From these properties, it can be deduced that the number of sign changes in p_0(x) in the interval [a,b) is w(a) - w(b). Here, w(c) means the number of sign changes in p_0(c), p_1(c), ... p_m(c) A sturm sequence can easily be constructed using polynome division. For details: see J. Stoer, R. Bulirsch "Introduction to Numerical Analysis". The number of sign changes between a and b equals the number of roots between a and b. So we could use binary chop too: after we've divided [a,b) into [a,c) and [c,b) we can check the number of signchanges in [a,c) and [c,b), until the number of signchanges is one, and then we're sure that one root is sitting in the interval. 3d degree equations are solved using using Cardano's method. It is numerically unstable with double roots. How does it work? Suppose we have an cubic equation ax^3+ bx^2 + cx + d = 0 After division by a, we get x^3 + b' x^2 + c' x + d' = 0 After substitution x = y -b'/3. We get y^3 = 3py - 2q (1) For certain p and q. This is the big Cardano trick: we could solve the equation if we would find u and v such that u^3 + v^3 = -2q and uv = p (2) since (u+v)^3 = u^3 + 3u^2v + 3v^2u + v^3. = 3(u+v) uv + u^3 + v^3 and y would be y = u+v. (2) turns out to be a quadratic equation, and it gives us one solution for (1). If (2) has no solution (discriminant 4q^2 - 4p^3 < 0), an other method has to used. We can safely assume that y = 2sqrt(p) cos(theta), and (1) turns out to be cos(3 theta) = -q/(p*(sqrt(p))) This gives us 3 solutions. `grids.c' Keeps trak of distribution raytracing grids and sampling them. `bsp.c' Binary space partitioning efficiency scheme. Hacked from Graphics Gems III. `optimise.c' Manipulate lists of objects to be optimised. `shade.c' Compute the color of a ray using textures, light_sources etc. This used to be the best preserved part of the original Ray raytracer. But Shawn McHorse revised it completely to allow TIR, microfacets, etc. This file recursively calls `trace()' `imagemap.c' Stuff for imagemaps: reading TGAs, mapping planes onto various shapes, and (of course) standard methods. `gif.c' The code for reading gif files. This file was snatched from a Linux Gif viewer. It was created by Harm Hanemaayer <hhanemaa@cs.ruu.nl>, and it was based on posting in rec.games.programmer in the spring of 1993. `ibuf.c' This implements a smart depth queue for keeping intersection information. `texture.c' Texture manipulations. `camera.c' Routines for manipulating cameras. Not very useful, tho. Source Description 2 ===================== The files below are files with object and shape standard_routines. The file xxx.c usually contains: `free_xxx()' free a xxx structure (and it's components) `get_new_xxx_object()' alloc and init a xxx structure (don't alloc components) `rotate_xxx(),' `scale_xxx(),' `translate_xxx()' transform a xxx structure `all_xxx_intersections()' intersect a ray with a xxx structure, and put some or all intersections into a queue. Give info, wether ray.pos is inside shape. `xxx_normal' the normal to a xxx shape. `copy_xxx' copy a xxx structure (and it's components) `inside_xxx' is a point inside an xxx shape? `precompute_xxx' Compute constants for a certain object before tracing has started, but after the parsing. Objects should be automatically bounded here. `print_xxx' Print useful information about a xxx, very useful for debugging. These routines are stored in a method structure. With each instance of a XXX, a pointer to XXX's methods is stored. So a sphere object carries a pointer to its own special routines. These routines can only be accessed using this method structure, since the routines are `PRIVATE'. If you want to add your own primitive this is what you have to do: 1. Make your own routines, and put them into a seperate file. Take a look at the implementation of some simple shapes, such as polygon, or sphere. Use `stub.c' as a starting point. 2. Add the new datastructures to `objects.h' 3. define the syntax of your primitive, and please make it POV like. Add it to the shape_block. Add the keywords to `token.c' and `rayparse.y'. Here are fragments to get you started: /* rayparse.y */ /* token declarations */ %type <objectval> XXXX_block XXXX_body %token XXXX_T %token <dectabptr> XXXX_IDENTIFIER /* syntax */ XXXX_body: /* how to specify a XXXX */ { $$ = get_new_XXXX_object(); /* no precomputation here! */ } | XXXX_body TRANSLATE vexp { translate_object($$, $3); } | XXXX_body ROTATE vexp { matrix rm; make_rotation_matrix(rm,$3);rotate_object($$, rm); } | XXXX_body scale_stuff { scale_object($$, $2); } | XXXX_body INVERSE { $$->inverted = !$$->inverted; } | XXXX_body texture_block { $$->text = $2; } ; XXXX_block: XXXX_T '{' XXXX_body '}' { $$ = $3; } ; shape_block: /* ... */ | XXXX_block {$$ = $1 } ; /* token.c, keyword table (it's in alfabetical order) */ { : : XXXX_T, "xxxx", /* remember! sorted by alphabet */ : : } 4. You're finished! Presto! Test your primitive, and then mail the modified sources to me. `box.c' Rectangular boxes. It also contains a public procedure `intersect_rawbox()', for intersecting a ray with an axis aligned box. The algorithm is standard. This function is public, because it could be used for bounding shapes. `composite.c' A composite is just a bunch of objects which can be treated as one. This makes collective scaling, rotating etc. very easy. Note that in Rayce, this is something different than a CSG union. `lights.c' A very simple file with routines for the lights objects. Code to create a linked list of all the lights in the scene is also here. This list is needed for efficiently finding the lights in the scene, in `shade.c' and `bg.c'. `plane.c' Manipulate infinite planes. `object.c' A uniform interface to the various shapes and object types in Rayce. `quadric.c' Code for arbitrary quadrics. `sphere.c' Spheres, the most basic thing in raytracing (along with checkered floors ;-) (gee, I must do checkers, some time) `superq.c' Superquadrics. It should work now. `torus.c' Toruses. Simple toruses. They can be calculated quite efficiently, because it is possible to have very tight bounds around them. Uses `solve.c' to do the equation solving. `csg.c' Code for CSG unions and intersections. Since the code for both overlaps, they are contained in one file. Mathematically speaking, they are even equivalent! `algebraic.c' Arbitrary algebraic surfaces. The general idea is: store the polynomial in terms of operations (similar to hoc level 4, in The Unix Programming Environment, by Kernighan & Pike). This is done in `rayparse.y'. Then use a simple "virtual" stack machine to calculate the resulting polynomial in the ray parameter t. The normal is calculated in a similar fashion: the input is vector Loc, and of all operands (which are polynomials p_j), the polynomial p_j(x1,x2,x3) in Loc is evaluated, and the polynomial dp_j/dx_i (i = 1...3) is evaluated in Loc. We then get the gradient of the polynomial Phi(x,y,z) which determines the surface normal `polygon.c' Flat polygons. Convex polygons are implemented by clipping a plane with the edges of a polygon. The polygon is projected onto a coordinate plane before it is clipped. Concave: ripped from MTV, it uses the Jordan Curve theorem `extrusion.c' Translational extrusions of 2D curves. This takes the intersection of a shape with the XY plane, and then "thickens" it along the Z axis. I have concocted the algorithm myself, but it turns out Kajiya and van Wijk already did it before me. `triangle.c' Smooth and non-smooth triangles. It works by decomposing an intersection point into barycentric coordinates. `conic.c' conic extrusion. Me *** About the author: I am a student, as of today (Januari 15 '94) I am 19, and I study applied mathematics at the Eindhoven University of Technology, in the Netherlands. I am in my second year, and I spend too little time on my study. Oh well. Raytracing is my hobby. If I am not spending my time behind my computer I also play the French horn and the piano. The following have been helpful in developing Rayce: * the sources to MTV, POV, Rayshade, Vort, Ray, Graphics Gems * The fractal.028 and PCGNet Raytracing echo community for making me happy with mail. * "Tutorial: Computer Graphics: Image Synthesis", Kenneth I Joy, a.o. ISBN 0-8186-8854-4. * "Three Dimensional Computer Graphics", Alan Watt, Addison Wesley. * "Advanced Rendering and Animation Techniques", Alan Watt & Mark Watt, Addison Wesley. * Linus Torvaldsen, for creating Linux, an excellent free Unix operating system for the 386/486 PCs. Try it! It's the best thing since sliced bread (The next best thing after linux being Rayce, of course! :) * A lot more books, after a while, I didn't check any titles. If you want a recommendation: here are some: - Glassners book "An intro to RayTracing." The best book on raytracer-writing available - "Advances in Computer Graphics IV. " These proceedings contain a good introductory paper on Ray tracing If you want something implemented, or if you want to hack something yourself: please contact me, so other people can benefit from it too. I also appreciate any comment on the Rayce, its sources and its docs. I hope that all mathematics were understandable, and that my English doesn't show that I normally speak Dutch. Send your compliments, beer, bugreports and daughters to: Han-Wen Nienhuys Dommelseweg 1A 5581 VA Waalre The Netherlands But email is preferred for the compliments and bugreports, of course: hanwen@stack.urc.tue.nl If you can't find me there, then try my dad's account: wsadjw@urc.tue.nl If you are connected to fidonet, then you can reach me at 2:284/102.27 My PCGNet address is 9:580/203.56 You could also try post a message to GRAPHICS, the international fidonet graphics echo. I regularly read the PCGNet raytracing echo, and I am subscribed to the DKB-L mailing list. I will try to have the latest version of Rayce available at Bennekom BBS: fido node 2:283/203, PCGNet 9:580/203, tel. 31-8389-15331. (freqqing times: 07.30 to 01.00, local time in Holland) Bennekom BBS supports V32bis and V42bis. `wuarchive.wustl.edu:/graphics/graphics/ray/rayce' Bugs ***** Yes. But seriously :), I am not a big tester myself. It is almost certain that Rayce contains bugs; while developing a complicated scene, you will probably encounter some. Maybe you will see assert failed file XXX.c, line XXX These are messages you shouldn't ever get to see, they show that some internal consistency check failed. If you see this, then please mail a bugreport to me. (On the other hand, if it came from `csg.c', you are probably not using correct shapes. Make sure extrusions and cylinders are closed, and use the `closed' keyword correctly on algebraics) If Rayce crashes, that's obviously subversive behaviour of Rayce. Especially if the crashes are violent, you should report them. If you find very subtle bugs, I am also very interested. On the average, it takes me two new versions before I discover those kind of errors. I should do more testing. Yes. I know. But coding is so much more fun. Known bugs: * The conic extrusion is BETA. It doesn't work. * Some algebraics don't render correctly. This is probably caused by the root finder, which was copied from Vort almost verbatim. * Some algebraics have singular points, where there is no normal to the surface (the normal is <0,0,0> ). When this happens, NNV # XXX.c is printed, with line number and the file where it happened. * Some algebraics aren't fun to calculate precisely. If you use sturm sequences, you will sometimes see solve.c scream if you use the runtime warnings turned on (`-d4'). This happens because the sturm code first tries a fast way of calculating a root. Check out the files `ONEWS' and `ChangeLog' on resolved bugs, and `TODO' on stuff that needs to be done. Distribution Raytracing ************************ Detailed information on what distribution ray tracing is can be found in the paper by Cook, Porter and Carpenter: "Distributed Ray Tracing", ACM Computer Graphics, Vol.18, Num.3, July 1984. [Note: what follows is a interpretation of what I think distributed raytracing is, so no garantuee is made that it is correct. ] Distribution raytracing is a process used to model "fuzzy" phenomena, such as soft shadows, focal blur, motion blur, fuzzy reflections and fuzzy refractions. In raytracing, refractions usually are crystal clear, and and reflections look unrealistically crisp. The shadows have sharp edges. Although this is good for generating nifty pictures, it is not realistic. In the real life, shadows don't have these sharp edges, and you cannot comb your hair using a teaspoon as a mirror. Let's take a closer look at this spoon. The surface of this spoon is scratched and bumped. Indeed, if you would look at the surface through a microscope you'd see a pretty wobbly surface. So not all of the light falling on the metallic surface will be reflected in the same direction. Since light works bidirectional, this also means that eyerays cast onto the surface don't generate one single reflection ray, but a huge number of "small" reflection rays, all in slightly different directions. The light of a reflection we're searching for is the sum of all these tiny contributions from various directions. Mathematically speaking: the intensity I of the incoming light at a point P, is a function of the direction D from which the light is coming, and of the location on the surface (P), so I = I(D, P) Because the surface is bumped, the light coming from a direction D will be reflected in P for percentage dependent on: D, the "theoretical" reflection direction R, and the surface normal N at P. So the reflection percentage r is: r (D, N, R) So what we will be seeing of a reflected light from a certain direction is r (D, N, R) * I (D) And the total reflection is the sum of all these tiny bits: total = Integral I(D)*r(D,N,R) all directions D Of course in practical situations, this mathematical descriptions isn't gonna help us. However, we could aproximate the above integral by carefully choosing a few (say 16) directions D, and summing all contributions: total = 1/16 Sum I(D) * r(D,N,R) ~ some directions D This is the process which is modeled via "distribution" raytracing: instead of one, multiple reflection rays are spawned off the surface of our spoon. In effect, we are taking discrete samples of the "real" reflection I*r, which is a continuous function. In Rayce penumbra, and fuzzy refraction is also modelled in this way. There is one caveat: If we would spawn N rays at each intersection point for determining the fuzzy reflection, refraction or shadow, then we would be tracing O((2N)^recursion_depth) rays. If we'd have complex scenes, rendering would take a really LONG time. So instead Rayce shoots a fixed number of eyerays. All these eyerays are sampled differently at each intersection point (this is called multidimensional sampling. Sounds good, huh? :-). At present, the rays are sampled from a jittered rectangular uniform grid, and results are modulated with a filter Of course, you could do the sampling with one eyeray only. But then the blur won't be so good since Rayce evaluates the color of the ray with only one try. The more samples the better, but if you use a higher resolution, then less samples per pixel suffice. `refl_diffuse' and `refr_diffuse' produce non-sharp reflections and refractions. The argument is in degrees. Anything less than 15 or 20 is good, altough the closer to zero the better you can see it. `radius' produce lights that cast soft shadows Focal blur hasn't been done (yet). Intersecting hyperspheres with rays. ************************************* [submitted to RTN, april 94 issue] In raytracing, we're interested in intersecting rays (halflines) with various shapes. One of these shapes is the hypersphere. It is defined by this equation: |x_1|^q + ... + |x_n|^q = 1 q > 1, (x_1, ..., x_n)in R^n if we define the q-norm by ||x|| = |x_1|^q + ... + |x_n|^q (q > 1) then this shape can be written easily as ||x|| = 1. Our problem is to find t such that || td + p || = 1 for given d,p in R^n This problem can be split in two subproblems: determining existence of a solution, and finding the solution itself. When |t| tends to infinity, then ||td+p|| also becomes large. We can therefore restrict ourselves to investigating the behaviour of the function ||x(t)|| on an interval [l, h]. This is a compact set, and since ||x|| is always positive, it must have a global minimum, for some t_0, with ||x(t_0)|| >= 0. If this minimum is larger than 1, then ||x(t)|| will be even bigger for all other t; if we find that the minimum is larger than one, we can stop searching immediately. On the other hand, if the minimum is less than one, a t_0 must exist for which ||x(t_0)|| = 1 exactly. This follows from the fact that ||x(t)|| is continuous and ||x(t)|| goes to infinity for t going to infinity. So now we have to find the minimum of ||x(t)||. A natural line of work is setting the derivative to zero. This has problems. If the derivative is zero, this only an indication, not a guarantee that a function has in fact got a minimum. For justifying this approach we need to take closer look at ||x(t)||. We remind that a convex function on a set S, is a function f for which f(A t_0 + (1-A)t_1) <= A f(t_0) + (1-A)f(t_1) 0 < A < 1, for all t_0, t_1 in S, i.e. if you consider f on an interval [t_0,t_1], then f is smaller than its linear interpolation on t_0 and t_1. If we have strict inequality in the definition, we usually say that f is strictly convex. The function x -> |x|^q (x in R) is convex for q >= 1 and if q > 1 we get strict convexity. The function t -> at+b (a,b in R) is convex. It can be proved that the composition of a convex function and a strictly convex one is also strictly convex. The sum of two convex functions will also be convex. Therefore t -> |td_1 + p_1|^q + |td_2 + p_2|^q + ... + |td_n + p_n|^q (q > 1) written shortly as t -> ||td + p|| is a strictly convex function on R LEMMA. A strictly convex differentiable function has an strictly increasing derivative. For a proof, check out any good book on real analysis. As a consequence of this lemma, such a function must have a positive second derivative, and it can have no more than one local minimum in R. So if we have ||x(t)||' is zero, we automatically have found the minimum. Since we already know that a minimum always exists, it should always be possible to find such a point. This explanation justifies the following algorithm for finding an intersection with a superquadric: 1. Find an interval which encloses the intersection, e.g. the intersection of the ray with a unit cube. If it misses the cube, then exit, there will be no intersection. 2. Using bisection, find the minimum of || td + p ||, ie the zero of its derivative (grad ||x|| , d). In this case, we have grad ||x|| = (q sgn (x_1) |x_1|^(q-1), .. , q sgn(x_n) |x_n|^(q-1) ). Here you should take x = td+p. ( . , .) is my favourite notation for the dot product. 3. Is this minimum bigger than one? Exit, there is no intersection. 4. In 1. we've found two points for which ||td + p|| > 1 holds. Now we have a t for which ||td + p|| < 1 . Using bisection we're able to find the two ts for which ||td + p|| = 1. There are a lot of tweaks possible, but this is the basic algorithm. Here are some straightforward optimisations and extensions: In step one, you could use a better algorithm than bisection, eg. Regula Falsi. * In step four, you can use Newton-Raphson's method, the convexity of is a sufficient condition for convergence. Use the intersections found in step 1. as starting points. Since ||x|| can be easily calculated from grad ||x||, this is pretty efficient: ||x|| = (grad ||x||, v) and v = (1/q)(x_1, ..., x_n) * In raytracing, we're only interested in the least positive solution, this allows you to get away cheaply if the starting point of the ray is inside the shape. * The algorithm only relies on the convexity and the existence of a minimum of ||td + p||. This algorithm therefore generalizes to a whole class of shapes, formed by a function f:R^n -> R, f(x) = 1, with f(td+p) convex, and minimal for some t = t_0. An obvious choice for f would be x_1^(p_1) + x_2^(p_2) + \dots + x_n^(p_n) (p_i > 1) leading to hypercylinders. * Example: In 3D space, |x|^2 + |y|^2 + |z|^4 = 1 defines a cylinder with rounded edges parallel to the Z-axis. An implementation of this algorithm can be found in Rayce, a raytracer by Y.T. It is available from `wuarchive.wustl.edu: /graphics/graphics/ray/rayce/'. Rayce has the original TeX document included Concept Index ************** * Menu: * : Compiling. * -DDEBUG: Invoking Rayce. * Algebraic surfaces: Primitive Shapes. * Algebraic surfaces: Primitive Shapes. * Ambient: Textures. * Angle: Textures. * Black Dots: Primitive Shapes. * Bounding shapes: Objects. * Box: Primitive Shapes. * Bugs: Bugs. * Camera: Camera. * Clipping Shapes: Objects. * Colors: Basic stuff. * compatibility, POV: POV compatibility. * Compatibility, POV: Textures. * Composites: Objects. * Conic extrusion: Non-Primitive Shapes. * Copyright: Copying. * Credits: Credits. * Csg: Non-Primitive Shapes. * Csg Part: Non-Primitive Shapes. * Cylinder: Primitive Shapes. * Debugging: Invoking Rayce. * Declare: Special Commands. * Define: Special Commands. * Diffuse: Textures. * Discs: Primitive Shapes. * Distribution raytracing: Distribution Raytracing. * Distribution raytracing: Objects. * Distribution raytracing: Options. * Extrusion: Non-Primitive Shapes. * features: Introduction. * Float: Basic stuff. * Gloss: Textures. * High order surfaces: Primitive Shapes. * Imagemapping: Textures. * Including files: Special Commands. * Index of refraction: Textures. * Input: Input Language. * Intersection: Non-Primitive Shapes. * Introduction: Introduction. * Inverse: Non-Primitive Shapes. * Invoking: Invoking Rayce. * Ior: Textures. * Known bugs: Bugs. * Language: Input Language. * Light intensity: Primitive Shapes. * Light source: Primitive Shapes. * Microfacets: Textures. * Missing Features: Introduction. * Motion Blur: Objects. * Non-Primitive Shapes: Non-Primitive Shapes. * Options: Options. * Options: Invoking Rayce. * Patch: Primitive Shapes. * Plane: Primitive Shapes. * Polygon: Primitive Shapes. * Polynomial surfaces: Primitive Shapes. * Polynomial surfaces: Primitive Shapes. * Porting scenes: POV compatibility. * POV: POV compatibility. * Primitives: Primitive Shapes. * Programming: Technical Stuff. * Quadric: Primitive Shapes. * Reflection: Textures. * Refraction: Textures. * Rotate: Non-Primitive Shapes. * Rotate: Primitive Shapes. * Roughness: Textures. * Scale: Non-Primitive Shapes. * Scale: Primitive Shapes. * Shadow Tolerance: Options. * Smooth triangle: Primitive Shapes. * Special Commands: Special Commands. * Specular: Textures. * Sphere: Primitive Shapes. * Superquadric: Primitive Shapes. * Surface characteristics: Textures. * Tech details: Technical Stuff. * Texture Hierarchy: Textures. * Texturemapping: Textures. * Textures: Textures. * Tolerance: Options. * Torus: Primitive Shapes. * Transformations: Non-Primitive Shapes. * Transformations: Primitive Shapes. * Translate: Non-Primitive Shapes. * Translate: Primitive Shapes. * Translucency: Textures. * Triangle: Primitive Shapes. * Union: Non-Primitive Shapes. * Vectors: Basic stuff. * Zits: Primitive Shapes.